/*
 * @lc app=leetcode.cn id=15 lang=cpp
 *
 * [15] 三数之和
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

// @lc code=start
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;         // 保存结果的数组

        sort(nums.begin(), nums.end());     // 对原数组进行排序

        // 枚举第一个元素
        for (int first = 0; first < nums.size(); first++) {
            // 如果不是第一个元素，且与上一个元素相同，则跳过
            if (first != 0 && nums[first] == nums[first - 1]) continue;

            int third = nums.size() - 1;
            int target = -nums[first];

            // 枚举第二个元素
            for (int second = first + 1; second < nums.size(); second++) {
                // 如果不是第一个元素，且与上一个元素相同，则跳过
                if (second != first + 1 && nums[second] == nums[second - 1]) continue;

                // 左移第三个指针
                while (third > second && nums[second] + nums[third] > target) {
                    third--;
                }

                // 不存在符合 target 的情况
                if (second == third) break;

                // 存在符合 target 的情况，进行记录
                if (nums[second] + nums[third] == target) {
                    result.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        
        return result;
    }
};
// @lc code=end

